class Solution(object):
    def minRemoveToMakeValid(self, s):
        n = len(s)
        st = []
        rm = []
        for i in range(n):
            if s[i] == '(':
                st.append(i)
            if s[i] == ')':
                if st:
                    st.pop()
                else:
                    rm.append(i)
        st += rm
        st.sort()
        if not st:
            return s
        t = ''
        for i in range(len(st)):
            if i == 0:
                t += s[:st[i]]
            else:
                t += s[st[i - 1] + 1:st[i]]
        t += s[st[-1] + 1:]
        return t
